Cours 2.11.1 du Mastère de Recherches en Informatique
Algorithmes avancés - Nicolas Schabanel
Cours n°1 - Partie A/C
Introduction aux algorithmes d'approximation
• NP-complétude, PCP et Inapproximabilité
• Définitions: Problèmes d'optimisation et approximation
• Inapproximabilité du TSP non-métrique
• Une 2-approximation pour le TSP métrique
• Une 3/2-approximation pour le TSP métrique
TD n°1
• Dérandomisation par la méthode de l'espérance conditionnelle appliquée à Max-Cut
• Une O(√n)-approximation pour le coloriage de graphes 3-coloriables
